polylabel

What is polylabel?

The polylabel npm package is used to find the pole of inaccessibility of a polygon, which is the most distant internal point from the polygon's edges. This is useful for placing labels on polygons in a way that maximizes readability and avoids overlap with the edges.

What are polylabel's main functionalities?

Finding the pole of inaccessibility

This feature allows you to find the pole of inaccessibility for a given polygon. The code sample demonstrates how to use the polylabel function to find the optimal label position within a square polygon.

const polylabel = require('polylabel');
const polygon = [[[0, 0], [10, 0], [10, 10], [0, 10], [0, 0]]];
const precision = 1.0;
const labelPosition = polylabel(polygon, precision);
console.log(labelPosition); // Outputs: [5, 5]

Other packages similar to polylabel

turf

Turf is a powerful geospatial analysis library for JavaScript. It provides a wide range of spatial operations, including finding the centroid of a polygon, which can be used for label placement. However, Turf does not specifically focus on finding the pole of inaccessibility like polylabel does.

d3-geo

D3-geo is a module of the D3.js library that provides geographic projections and related utilities. It can be used to calculate the centroid of a polygon, which is useful for label placement. Unlike polylabel, d3-geo does not specifically target the pole of inaccessibility.

README

polylabel

A fast algorithm for finding polygon pole of inaccessibility, the most distant internal point from the polygon outline (not to be confused with centroid), implemented as a JavaScript library. Useful for optimal placement of a text label on a polygon.

It's an iterative grid algorithm, inspired by paper by Garcia-Castellanos & Lombardo, 2007. Unlike the one in the paper, this algorithm:

• guarantees finding global optimum within the given precision
• is many times faster (10-40x)

How the algorithm works

This is an iterative grid-based algorithm, which starts by covering the polygon with big square cells and then iteratively splitting them in the order of the most promising ones, while aggressively pruning uninteresting cells.

1. Generate initial square cells that fully cover the polygon (with cell size equal to either width or height, whichever is lower). Calculate distance from the center of each cell to the outer polygon, using negative value if the point is outside the polygon (detected by ray-casting).
2. Put the cells into a priority queue sorted by the maximum potential distance from a point inside a cell, defined as a sum of the distance from the center and the cell radius (equal to cell_size * sqrt(2) / 2).
3. Calculate the distance from the centroid of the polygon and pick it as the first "best so far".
4. Pull out cells from the priority queue one by one. If a cell's distance is better than the current best, save it as such. Then, if the cell potentially contains a better solution that the current best (cell_max - best_dist > precision), split it into 4 children cells and put them in the queue.
5. Stop the algorithm when we have exhausted the queue and return the best cell's center as the pole of inaccessibility. It will be guaranteed to be a global optimum within the given precision.

JavaScript Usage

Given polygon coordinates in GeoJSON-like format and precision (1.0 by default), Polylabel returns the pole of inaccessibility coordinate in [x, y] format.

var p = polylabel(polygon, 1.0);

TypeScript

TypeScript type definitions are available via npm install --save @types/polylabel.

C++ Usage

It is recommended to install polylabel via mason. You will also need to install its dependencies: geometry.hpp and variant.

#include <mapbox/polylabel.hpp>

int main() {
    mapbox::geometry::polygon<double> polygon = readPolygon(); // Get polygon data from somewhere.
    mapbox::geometry::point<double> p = mapbox::polylabel(polygon, 1.0);
    return 0;
}

Ports to other languages

• andrewharvey/geojson-polygon-labels (CLI)
• Twista/python-polylabel (Python)
• Shapely (Python)
• polylabelr (R)
• polylabel-rs (Rust)